As processor performance has improved, memory systems that provide instructions and/or data to a processor have not achieved similar performance increases. One reason is that the clock speed of a processor can be increased at a greater rate than the clock speed of the memory systems. Memory systems are limited by external busses that supply instructions and data to the processor from external memory, which takes time. As a result, the processor may be idle while waiting for data. To improve processor performance, cache memories have been used to store local copies of data (e.g. within the processor or within the same chip) that may be accessed more quickly than data in an external memory.
A cache memory can improve processor performance for two reasons. First, an address recently accessed will likely be accessed again, so storing the data in a cache memory will make it likely that the data associated with the address is available upon subsequent accesses to the same memory location. Second, data located in memory near a currently accessed data will likely be requested soon after the currently accessed data. Performance can be improved by retrieving the currently accessed data as well as nearby data and storing them both in the cache memory. Later, when data near the previously accessed data is needed, the data will already be available from the cache memory.
Cache memory is typically partitioned into banks (or blocks) and addresses of a memory space are mapped onto the cache banks. When an address maps to more than one bank, to save time all the banks are speculatively accessed to return data that may or may not correspond to the address. The extra speculative accesses consume additional power and resources. When the correct bank has been determined, only the correct data is forwarded to the requesting device and the work performed by accessing the wrong banks is discarded.
A cache is smaller than main memory and will fill up as data is stored into the cache memory. When a cache memory is full, a decision must be made as to which cache data will be removed and replaced with new data. Various replacement methods are history based, for example, Least Recently Used, Not Recently Used, First in First Out). Pseudo random methods have also been used to select data to be replaced based on a combination of variables. However, these methods are non-deterministic and an address may be in one bank at one time and in a different bank at a different time. Thus multiple wrong accesses to tag banks are made before a cache hit or miss can be determined. A more efficient cache memory may be desired.